package com.jiawei.栈;

/**
 * @author : willian fu
 * @version : 1.0
 * 栈的特性，先入后出(数组实现)
 */
public class ArrayStack<E> implements Stack<E> {

    //最大栈深
    private static final int MAX_SIZE = Integer.MAX_VALUE;

    //初始栈深
    private static final int INIT_SIZE = 10;

    //扩容因子
    private static final double EXPAND = 0.5;

    private Object[] stack;

    //栈指针
    private int pointer = 0;

    ArrayStack(int capacity) {
        this.stack = new Object[capacity];
    }

    ArrayStack() {
        this.stack = new Object[MAX_SIZE];
    }

    /**
     * 出栈
     *
     * @return
     */
    @Override
    public E pop() {
        if (pointer > 0) {
            E data = (E)this.stack[this.pointer - 1];
            this.pointer--;
            return data;
        }
        return null;
    }

    /**
     * 入栈
     *
     * @param val
     * @return
     */
    @Override
    public void push(E val) {
        if (this.stack.length <= this.pointer) {
            this.expandSpace();
        }
        this.stack[this.pointer] = val;
        this.pointer++;
    }

    /**
     * 输出栈元素
     */
    @Override
    public void print() {
        System.out.println("当前栈深: " + this.stack.length);
        if (this.pointer <= 0){
            System.out.println("栈内无数据 *_*||");
        }
        for (int i = this.pointer - 1; i >= 0 ; i--) {
            System.out.println(i + ":[" + this.stack[i].toString() + "]  ");
        }
    }

    /**
     * 栈空间扩容，防止溢出
     *
     * @return
     */
    private void expandSpace() {
        if (this.stack.length == MAX_SIZE) {
            throw new RuntimeException("数组容量已到极限");
        }
        int afterSize = this.stack.length + (int) (this.stack.length * EXPAND);
        //限制最大容量
        if (afterSize > MAX_SIZE) {
            afterSize = MAX_SIZE;
        }
        Object[] object = new Object[afterSize];
        System.arraycopy(this.stack, 0, object, 0, this.pointer);
        this.stack = object;
    }
}
